// 版权所有2011 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 包bzip2实现bzip2解压。
package bzip2

import "io"

// bzip2没有RFC。我使用维基百科页面作为参考，并进行了大量猜测：https:
// pyflate的源代码对调试很有用：
// http:

// 当发现bzip2数据在语法上无效时，返回结构错误。
type StructuralError string

func (s StructuralError) Error() string {
	return "bzip2 data invalid: " + string(s)
}

// 读卡器解压缩bzip2压缩数据。
type reader struct {
	br           bitReader
	fileCRC      uint32
	blockCRC     uint32
	wantBlockCRC uint32
	setupDone    bool // 如果我们分析了bzip2头，则为true。
	blockSize    int  // 以字节为单位的块大小，即900*1000。
	eof          bool
	c            [256]uint // 逆BWT的`'C'数组。
	tt           []uint32  // 镜像bzip2源中的``tt'数组，并在高24位中包含P数组。
	tPos         uint32    // tt中下一个输出字节的索引。

	preRLE      []uint32 // 包含仍需处理的RLE数据。
	preRLEUsed  int      // 使用的preRLE条目数。
	lastByte    int      // 看到的最后一个字节值。
	byteRepeats uint     // 看到的lastByte的重复次数。
	repeats     uint     // 要输出的lastByte的副本数。
}

// NewReader返回一个io。从r.
// 解压bzip2数据的读取器，如果r不实现io。ByteReader，
// 解压器可能会从r读取超过必要的数据。
func NewReader(r io.Reader) io.Reader {
	bz2 := new(reader)
	bz2.br = newBitReader(r)
	return bz2
}

const bzip2FileMagic = 0x425a // “BZ”
const bzip2BlockMagic = 0x314159265359
const bzip2FinalMagic = 0x177245385090

// 安装程序解析bzip2报头。
func (bz2 *reader) setup(needMagic bool) error {
	br := &bz2.br

	if needMagic {
		magic := br.ReadBits(16)
		if magic != bzip2FileMagic {
			return StructuralError("bad magic value")
		}
	}

	t := br.ReadBits(8)
	if t != 'h' {
		return StructuralError("non-Huffman entropy encoding")
	}

	level := br.ReadBits(8)
	if level < '1' || level > '9' {
		return StructuralError("invalid compression level")
	}

	bz2.fileCRC = 0
	bz2.blockSize = 100 * 1000 * (level - '0')
	if bz2.blockSize > len(bz2.tt) {
		bz2.tt = make([]uint32, bz2.blockSize)
	}
	return nil
}

func (bz2 *reader) Read(buf []byte) (n int, err error) {
	if bz2.eof {
		return 0, io.EOF
	}

	if !bz2.setupDone {
		err = bz2.setup(true)
		brErr := bz2.br.Err()
		if brErr != nil {
			err = brErr
		}
		if err != nil {
			return 0, err
		}
		bz2.setupDone = true
	}

	n, err = bz2.read(buf)
	brErr := bz2.br.Err()
	if brErr != nil {
		err = brErr
	}
	return
}

func (bz2 *reader) readFromBlock(buf []byte) int {
	// bzip2是一个基于块的压缩器，只是它有一个运行长度
	// 预处理步骤。基于块的特性意味着我们可以预先分配固定大小的缓冲区并重用它们。然而，RLE 
	// 预处理需要分配巨大的缓冲区来存储
	// 最大扩展。因此，我们一次处理所有块，除了
	// 我们根据需要解压的RLE。
	n := 0
	for (bz2.repeats > 0 || bz2.preRLEUsed < len(bz2.preRLE)) && n < len(buf) {
		// 我们有RLE数据等待处理。

		// 运行长度编码的工作原理如下：
		// 任何四个相等字节的序列后面都跟一个长度
		// 字节，其中包含该字节到
		// include的重复次数。（重复次数可以为零。）因为我们是
		// 按需解压，所以我们的状态保存在读卡器
		// 对象中。

		if bz2.repeats > 0 {
			buf[n] = byte(bz2.lastByte)
			n++
			bz2.repeats--
			if bz2.repeats == 0 {
				bz2.lastByte = -1
			}
			continue
		}

		bz2.tPos = bz2.preRLE[bz2.tPos]
		b := byte(bz2.tPos)
		bz2.tPos >>= 8
		bz2.preRLEUsed++

		if bz2.byteRepeats == 3 {
			bz2.repeats = uint(b)
			bz2.byteRepeats = 0
			continue
		}

		if bz2.lastByte == int(b) {
			bz2.byteRepeats++
		} else {
			bz2.byteRepeats = 0
		}
		bz2.lastByte = int(b)

		buf[n] = b
		n++
	}

	return n
}

func (bz2 *reader) read(buf []byte) (int, error) {
	for {
		n := bz2.readFromBlock(buf)
		if n > 0 || len(buf) == 0 {
			bz2.blockCRC = updateCRC(bz2.blockCRC, buf[:n])
			return n, nil
		}

		// 街区结束。检查CRC。
		if bz2.blockCRC != bz2.wantBlockCRC {
			bz2.br.err = StructuralError("block checksum mismatch")
			return 0, bz2.br.err
		}

		// 找到下一个街区。
		br := &bz2.br
		switch br.ReadBits64(48) {
		default:
			return 0, StructuralError("bad magic value found")

		case bzip2BlockMagic:
			// 区块开始。
			err := bz2.readBlock()
			if err != nil {
				return 0, err
			}

		case bzip2FinalMagic:
			// 检查文件结尾的CRC。
			wantFileCRC := uint32(br.ReadBits64(32))
			if br.err != nil {
				return 0, br.err
			}
			if bz2.fileCRC != wantFileCRC {
				br.err = StructuralError("file checksum mismatch")
				return 0, br.err
			}

			// 向前跳到字节边界。
			// 是否有与此文件连接的文件？
			// 它将以BZ开头。
			if br.bits%8 != 0 {
				br.ReadBits(br.bits % 8)
			}
			b, err := br.r.ReadByte()
			if err == io.EOF {
				br.err = io.EOF
				bz2.eof = true
				return 0, io.EOF
			}
			if err != nil {
				br.err = err
				return 0, err
			}
			z, err := br.r.ReadByte()
			if err != nil {
				if err == io.EOF {
					err = io.ErrUnexpectedEOF
				}
				br.err = err
				return 0, err
			}
			if b != 'B' || z != 'Z' {
				return 0, StructuralError("bad magic value in continuation file")
			}
			if err := bz2.setup(false); err != nil {
				return 0, err
			}
		}
	}
}

// readBlock读取bzip2块。这个神奇的数字应该已经被消耗掉了。
func (bz2 *reader) readBlock() (err error) {
	br := &bz2.br
	bz2.wantBlockCRC = uint32(br.ReadBits64(32)) // 跳过校验和。TODO:看看我们能不能弄清楚是什么。
	bz2.blockCRC = 0
	bz2.fileCRC = (bz2.fileCRC<<1 | bz2.fileCRC>>31) ^ bz2.wantBlockCRC
	randomized := br.ReadBits(1)
	if randomized != 0 {
		return StructuralError("deprecated randomized files")
	}
	origPtr := uint(br.ReadBits(24))

	// 如果块中没有使用每个字节值（即文本），则
	// 符号集将减少。使用的符号存储为
	// 两级16x16位图。
	symbolRangeUsedBitmap := br.ReadBits(16)
	symbolPresent := make([]bool, 256)
	numSymbols := 0
	for symRange := uint(0); symRange < 16; symRange++ {
		if symbolRangeUsedBitmap&(1<<(15-symRange)) != 0 {
			bits := br.ReadBits(16)
			for symbol := uint(0); symbol < 16; symbol++ {
				if bits&(1<<(15-symbol)) != 0 {
					symbolPresent[16*symRange+symbol] = true
					numSymbols++
				}
			}
		}
	}

	if numSymbols == 0 {
		// 必须有EOF符号。
		return StructuralError("no symbols in input")
	}

	// 一个区块使用两到六棵不同的哈夫曼树。
	numHuffmanTrees := br.ReadBits(3)
	if numHuffmanTrees < 2 || numHuffmanTrees > 6 {
		return StructuralError("invalid number of Huffman trees")
	}

	// 哈夫曼树可以每50个符号切换一次，因此有一个
	// 树索引列表，告诉我们每50个符号块使用哪棵树。
	numSelectors := br.ReadBits(15)
	treeIndexes := make([]uint8, numSelectors)

	// 将树索引移动到前面，并转换为一元
	// 数字。
	mtfTreeDecoder := newMTFDecoderWithRange(numHuffmanTrees)
	for i := range treeIndexes {
		c := 0
		for {
			inc := br.ReadBits(1)
			if inc == 0 {
				break
			}
			c++
		}
		if c >= numHuffmanTrees {
			return StructuralError("tree index too large")
		}
		treeIndexes[i] = mtfTreeDecoder.Decode(c)
	}

	// 移动到前端转换的符号列表取自之前解码的符号位图。
	symbols := make([]byte, numSymbols)
	nextSymbol := 0
	for i := 0; i < 256; i++ {
		if symbolPresent[i] {
			symbols[nextSymbol] = byte(i)
			nextSymbol++
		}
	}
	mtf := newMTFDecoder(symbols)

	numSymbols += 2 // 为了解释RUNA和RUNB符号
	huffmanTrees := make([]huffmanTree, numHuffmanTrees)

	// 现在我们解码每个树的代码长度数组。
	lengths := make([]uint8, numSymbols)
	for i := range huffmanTrees {
		// 代码长度由5位基值进行增量编码。
		length := br.ReadBits(5)
		for j := range lengths {
			for {
				if length < 1 || length > 20 {
					return StructuralError("Huffman length out of range")
				}
				if !br.ReadBit() {
					break
				}
				if br.ReadBit() {
					length--
				} else {
					length++
				}
			}
			lengths[j] = uint8(length)
		}
		huffmanTrees[i], err = newHuffmanTree(lengths)
		if err != nil {
			return err
		}
	}

	selectorIndex := 1 // 下一个使用
	if len(treeIndexes) == 0 {
		return StructuralError("no tree selectors given")
	}
	if int(treeIndexes[0]) >= len(huffmanTrees) {
		return StructuralError("tree selector out of range")
	}
	currentHuffmanTree := huffmanTrees[treeIndexes[0]]
	bufIndex := 0 // 索引bz2的树索引。buf，输出缓冲区。
	// 移动到前端变换的输出是游程编码的，
	// 我们将解码合并到哈夫曼解析循环中。这两个
	// 变量累加重复计数。查看维基百科页面了解
	// 详细信息。
	repeat := 0
	repeatPower := 0

	// C数组（由反向BWT使用）需要初始化为零。
	for i := range bz2.c {
		bz2.c[i] = 0
	}

	decoded := 0 // 统计当前树解码的符号数。
	for {
		if decoded == 50 {
			if selectorIndex >= numSelectors {
				return StructuralError("insufficient selector indices for number of symbols")
			}
			if int(treeIndexes[selectorIndex]) >= len(huffmanTrees) {
				return StructuralError("tree selector out of range")
			}
			currentHuffmanTree = huffmanTrees[treeIndexes[selectorIndex]]
			selectorIndex++
			decoded = 0
		}

		v := currentHuffmanTree.Decode(br)
		decoded++

		if v < 2 {
			// 这是RUNA或RUNB符号。
			if repeat == 0 {
				repeatPower = 1
			}
			repeat += repeatPower << v
			repeatPower <<= 1

			// 这个200万的限制来自bzip2源代码
			// 代码。它可以防止重复溢出。
			if repeat > 2*1024*1024 {
				return StructuralError("repeat count too large")
			}
			continue
		}

		if repeat > 0 {
			// 我们已经解码了完整的行程长度，所以我们需要
			// 复制最后一个输出符号。这是EOF符号。因为它总是在移动到前台列表的末尾，而且永远不会移动到前台，所以它有这个唯一的值。
			if repeat > bz2.blockSize-bufIndex {
				return StructuralError("repeats past end of block")
			}
			for i := 0; i < repeat; i++ {
				b := mtf.First()
				bz2.tt[bufIndex] = uint32(b)
				bz2.c[b]++
				bufIndex++
			}
			repeat = 0
		}

		if int(v) == numSymbols-1 {
			break
		}

		// 由于两个元符号（RUNA和RUNB）的值分别为0和1，因此
		// 人们希望将| v-2 |传递给MTF解码器。
		// 然而，MTF列表的前面从来没有被引用为0，
		// 它总是被引用为运行长度为1。因此0 
		// 不需要编码，我们在下一行
		// 中有| v-1 |。
		b := mtf.Decode(int(v - 1))
		if bufIndex >= bz2.blockSize {
			return StructuralError("data exceeds block size")
		}
		bz2.tt[bufIndex] = uint32(b)
		bz2.c[b]++
		bufIndex++
	}

	if origPtr >= uint(bufIndex) {
		return StructuralError("origPtr out of bounds")
	}

	// 我们已经完成了熵解码。现在我们可以执行
	// 反向BWT并设置RLE缓冲区。
	bz2.preRLE = bz2.tt[:bufIndex]
	bz2.preRLEUsed = 0
	bz2.tPos = inverseBWT(bz2.preRLE, origPtr, bz2.c[:])
	bz2.lastByte = -1
	bz2.byteRepeats = 0
	bz2.repeats = 0

	return nil
}

// InverseEBWT按照
// http:
// 在该文档中，origPtr被称为“I”，c是
// 第一次传递数据后的“c”数组。这是一个论点，因为我们合并了第一个
// 过程和哈夫曼解码。
// 
// 这也实现了bzip2源代码
// 中的“单数组”方法，该方法将输出仍置乱，放在tt的底部8位，下一个字节的索引放在顶部24位。第一个字节的索引是
// 返回。
func inverseBWT(tt []uint32, origPtr uint, c []uint) uint32 {
	sum := uint(0)
	for i := 0; i < 256; i++ {
		sum += c[i]
		c[i] = sum - c[i]
	}

	for i := range tt {
		b := tt[i] & 0xff
		tt[c[b]] |= uint32(i) << 8
		c[b]++
	}

	return tt[origPtr] >> 8
}

// 这是一个与哈希/CRC32类似的标准CRC32，只是所有移位都是反向的，
// 导致输入中的位以与通常相反的顺序进行处理。

var crctab [256]uint32

func init() {
	const poly = 0x04C11DB7
	for i := range crctab {
		crc := uint32(i) << 24
		for j := 0; j < 8; j++ {
			if crc&0x80000000 != 0 {
				crc = (crc << 1) ^ poly
			} else {
				crc <<= 1
			}
		}
		crctab[i] = crc
	}
}

// updateCRC更新crc值以将数据合并到b中。
// 初始值为0。
func updateCRC(val uint32, b []byte) uint32 {
	crc := ^val
	for _, v := range b {
		crc = crctab[byte(crc>>24)^v] ^ (crc << 8)
	}
	return ^crc
}
